/*
 * @lc app=leetcode.cn id=82 lang=cpp
 *
 * [82] 删除排序链表中的重复元素 II
 */
#include <stack>
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
  public:
    ListNode *deleteDuplicates(ListNode *head)
    {
        ListNode *new_head = nullptr;
        std::stack<ListNode *> list_node;
        int pop_value = 200;

        while (head) {
            if (list_node.empty() && pop_value != head->val) {
                list_node.push(head);
            } else if (!list_node.empty() &&
                       head->val == list_node.top()->val) {
                list_node.pop();
                pop_value = head->val;
            } else if (pop_value != head->val) {
                list_node.push(head);
                pop_value = head->val;
            }

            head = head->next;
        }

        while (!list_node.empty()) {
            list_node.top()->next = new_head;
            new_head = list_node.top();
            list_node.pop();
        }

        return new_head;
    }
};
// @lc code=end
